package com.practice.recursive;

public class NextPermute {
	/**
	 * Return next permute number/string in sequence. If already highest,
	 * return null.
	 * 
	 * @param number
	 * @return
	 */
	public String nextPermute(String s) {
		int N = s.length();
		StringBuilder sb = new StringBuilder(s);
		
		int head = N - 2;
		while (head >= 0 && sb.charAt(head) >= sb.charAt(head+1)) head--;
		if (head < 0) return null;
		
		int tail = N - 1;
		while (sb.charAt(head) >= sb.charAt(tail)) tail--;
		
		char t = sb.charAt(head);
		sb.setCharAt(head, sb.charAt(tail));
		sb.setCharAt(tail, t);
		
		return sb.substring(0, head+1) + reverse(sb.substring(head+1, N));
	}
	
	private String reverse(String s) {
		return new StringBuilder(s).reverse().toString();
	}
	
	public static void main(String[] args) {
		NextPermute np = new NextPermute();
		int total = 1;
		String s = "111223";
		System.out.println(s);
		while ( (s = np.nextPermute(s)) != null) {
			total++;
			System.out.println(s);
		}
		
		System.out.println("Total = " + total);
	}
}
